package com.codingvip.tree;


import java.util.Arrays;

/**
 * @Author Tony.Han
 * @Created at 2020/4/2 2:54 下午
 * Desc:
 */
public class HeapSort {
    private int heapsize;
    public void heapSort(int a[]) {
        buildrMaxHeap(a);

        int step=1;
        for (int i = a.length - 1; i > 0; i--) {
            myswap(a, 0, i);
            heapsize--;
            System.out.println("STEP::::" + (step++) + "--->" + Arrays.toString(a));
            max_heapify(a, 0);
        }

    }

    public void max_heapify(int a[], int i) {
        int l = left(i);
        int r = right(i);
        int largest=i;
        if (l < heapsize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapsize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            myswap(a, i, largest);
            System.out.println("Max_heaify:::" + Arrays.toString(a));

            max_heapify(a,largest);
        }

    }

    public void buildrMaxHeap(int a[]) {
        for (int i = parent(heapsize - 1); i >= 0; i--) {
            max_heapify(a, i);
        }
    }

    public static void main(String[] args) {
        int[] aaaa = new int[]{3, 7, 2, 11, 3, 4, 9, 2, 18, 0};
        HeapSort heapSort = new HeapSort();
        heapSort.heapsize = aaaa.length;
        heapSort.heapSort(aaaa);

        System.out.println(Arrays.toString(aaaa));
    }




    private int parent(int i) {
        return (i - 1) / 2;
    }
    private void myswap(int[] a, int i, int largest) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
    }

    private int left(int i) {
        return i * 2 + 1;
    }

    private int right(int i) {
        return i * 2 + 2;
    }




}
